﻿#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    const int MOD = 1e9 + 7;
public:
    // 879. 盈利计划
    /*int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit)
    {
        int len = group.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));
        for (int j = 0; j <= n; j++)
            dp[0][j][0] = 1;

        for (int i = 1; i <= len; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= m; k++)
                {
                    dp[i][j][k] += dp[i - 1][j][k];
                    if (j >= group[i - 1])
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD;
                }
        return dp[len][n][m];
    }*/

    int profitableSchemes(int n, int m, vector<int>& group, vector<int>& profit)
    {
        int len = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int j = 0; j <= n; j++)
            dp[j][0] = 1;

        for (int i = 1; i <= len; i++)
            for (int j = n; j >= group[i - 1]; j--)
                for (int k = m; k >= 0; k--)
                {
                    dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[j][k] %= MOD;
                }
        return dp[n][m];
    }
};

int main()
{
    vector<int> g{ 2,2 };
    vector<int> p{ 2,3 };
    cout << Solution().profitableSchemes(5, 3, g, p) << endl;

    return 0;
}